package com.sharedlease.check;

public class KmpReview {

    private static int[] prefix_table(String patterns, int n){
        int[] prefix = new int[n];
        char[] pattern = patterns.toCharArray();
        prefix[0] = 0;
        int j = 0;
        for (int i = 1; i < n; i++){
            if (pattern[i] == pattern[j]){
                prefix[i] = j + 1;
                j++;
            }else {
                prefix[i] = 0;
                if (j > 0){
                    j = prefix[j - 1];
                    i--;
                }
            }
        }
        return prefix;
    }

    public static int find_pattern(String target, String pattern){
        int n = target.length(), m = pattern.length();
        int[] prefix_table = prefix_table(pattern, m);
        for (int i = 0, j = 0; i < n && j < m; i++) {
            if (target.charAt(i) == pattern.charAt(j)){
                j++;
                if (j == m){
                    return i - m + 1;
                }
            }
            else{
                if (j > 0) {
                    j = prefix_table[j - 1];
                    i--;
                }
            }
        }
        return -1;
    }

}
